home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 2681 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.5 KB
  1. Path: oxy.rust.net!usenet
  2. From: ebennett@rust.net
  3. Newsgroups: comp.lang.c
  4. Subject: Re: quick decision: is n a power of 2?
  5. Date: Tue, 23 Jan 1996 05:02:24 GMT
  6. Organization: Rust Net - High Speed Internet in Detroit  810-642-2276
  7. Message-ID: <4e1fim$do7@oxy.rust.net>
  8. References: <Pine.OSF.3.91.960119114608.18779E-100000@io.UWinnipeg.ca> <4dpian$gij@oxy.rust.net> <4drjkc$il4@news.gate.net> <4e0gd3INNa7s@keats.ugrad.cs.ubc.ca>
  9. NNTP-Posting-Host: liv-18.rust.net
  10. X-Newsreader: Forte Free Agent 1.0.82
  11.  
  12. c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku) wrote:
  13.  
  14. >In article <4drjkc$il4@news.gate.net>, William Hutto <bhutto@gate.net> wrote:
  15. > >In article <4dpian$gij@oxy.rust.net>, ebennett@rust.net spake:
  16. > >;Bill Simpson <wsimpson@uwinnipeg.ca> wrote:
  17. > >;
  18. > >;>Is there a fast way to decide whether a number n is a power of 2?
  19. > >;
  20. > >;
  21. > >;Working with positive numbers, a number will be a power of 2 if there
  22. > >;is exactly one bit set in the number.  (For negative numbers, you can
  23. > >;use the following by taking the abs() of the number).
  24. > >
  25. > >Negative numbers? The person in question wasn't asking for a power of -2. 
  26. > >Power of 2 has to be > 0 for integers.
  27. > >
  28. > >;
  29. > >;Given some number, there is a neat trick to generate a mask which will
  30. > >;have exactly one bit set in it.  The bit set will be the least
  31. > >;significant non-zero bit in the original number:
  32. > >;
  33. > >;    mask = ~number & number;
  34. > >
  35. > >It's faster just to use:
  36. > >
  37. > >mask = 0;
  38. > >
  39. > >;
  40. > >;Now, if number contained a single non-zero bit (and is therefore a
  41. > >;power of 2),  mask will be equal to number.  Therefore:
  42. > >;
  43. > >;   if (number == (~number & number))
  44.  
  45. >Umm, the bitwise AND is very much like the AND in truth functional logic.
  46.  
  47. >A statement like "I'm a newbie and I'm not a newbie" is called a contradiction
  48. >because it is always false. Analogously, taking a bitwise complement of a
  49. >number and AND'ing it with the original always produces zero.
  50.  
  51. >A:    0100
  52. >~A:    1011
  53. >------------
  54. >A ^ ~A: 0000
  55.  
  56. >-- 
  57.  
  58. My apologies for the confusion.  As has been pointed out, there was an
  59. error in my original post.  It was supposed to be:
  60.  
  61.    if (number == (-number & number))
  62.      etc.
  63.  
  64. Also, as pointed out, a check for 0 is required first, since this does
  65. not work for 0.  So, given a 2's complement implementation, and not
  66. worrying about negative powers of 2:
  67.  
  68.   bool isPowerOfTwo(long number)
  69.   {
  70.      if (number == 0)
  71.         return FALSE;
  72.      else
  73.      {
  74.         number = labs(number); 
  75.         return (number == (-number & number));
  76.      }
  77.   }
  78.  
  79. Define bool as you wish, and make the input whatever size integer is
  80. desired.
  81.  
  82. Earl
  83.  
  84.  
  85.  
  86.